#include <iostream>
#include <cstdio>
#include <stack>
#include <algorithm>
#include <vector>
#include <string>

using namespace std;
class Solution1 {
public:
    int getLongestPalindrome(string A, int n) {
        // write code here
        //中心扩散
        if(n<2){
            return n;
        }
        int maxlen=0;
        for(int i=0;i<n;){
            if(n-i <=maxlen/2){
                break;
            }
            int l=i,r=i;
            while(r<n-1 && A[r+1]==A[r]) r++; //后一个元素和当前一样
            i=r+1;
            while(l>0&&r<n-1 && A[l-1]==A[r+1]){
                l--;
                r++;
            }
            if(r-l+1>maxlen){
                maxlen=r-l+1;
            }
        }
        return maxlen;
    }
};
class Solution {
public:
    int getLongestPalindrome(string A, int n) {
        // write code here
        int len=A.size(),ans=0;
        vector<vector<bool>> dp(len+5,vector<bool>(len+5,false));
        
        for(int j=1;j<n;j++){
            for(int i=0;i<j;i++){
                if(A[i]!=A[j]) continue;
                if(i==j||j-i<=2){
                    dp[i][j]=true;
                }else{
                    dp[i][j]=dp[i+1][j-1];
                }
                if(dp[i][j] && j-i+1>ans){
                    ans=j-i+1;
                }
            } 
        }
        return ans;
    }
};
int main(){
    Solution s;
    cout << s.getLongestPalindrome("abc1234321ab",12) <<endl;


    return 0;
}